package com.zhouhong.LeetCode;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-02 11:10
 **/

public class LeetCode0011 {
    // 1. 枚举左柱子和右柱子，(x-y) * minHeight
    // 会超时 O(n^2)
    public int maxArea1(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length - 1; ++i) {
            for (int j = i + 1; j < height.length; ++j) {
                int area = (j - i) * Math.min(height[i], height[j]);
                max = Math.max(max, area);
            }
        }
        return max;
    }
    // 左右边界 i、j 向中间收敛，前后夹逼的方法
    // O(n)
    public int maxArea2(int[] height) {
        int max = 0;
        for (int i = 0, j = height.length - 1; i < j;) {
            int minHeight = height[i] < height[j] ? height[i ++]: height[j --];
            int area = (j - i + 1) * minHeight;
            max = Math.max(max, area);
        }
        return max;
    }
    // 方法二换一种写法
    // 左右边界 i、j 向中间收敛，前后夹逼的方法
    // O(n)
    public int maxArea3(int[] height) {
        int max = 0, i = 0, j = height.length - 1;
        while (i < j){
            // 如果左边的柱子小于右边的柱子，取之前的最大容水量和现在最低柱子求得的容水量的最大值赋值给最大容水量，左边指针右移
            if (height[i] < height[j]){
                max = Math.max(max, (j - i) * height[i]);
                i ++;
            }else {
                // 如果右边的柱子小于左边的柱子，取之前的最大容水量和现在最低柱子求得的容水量的最大值赋值给最大容水量，右边指针左移
                max = Math.max(max, (j - i) * height[j]);
                j --;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {1,8,6,2,5,4,8,3,7};
        System.out.println((new LeetCode0011()).maxArea3(arr));
    }
}
